
48
types. For the set ADT, we might have such operations as union,
intersection, size, and complement. Alternately, we might only want
the two operations union and find, which would define a different
ADT on the set.
The basic idea is that the implementation of these operations
is written once in the program, and any other part of the program
that needs to perform an operation on the ADT can do so by calling
the appropriate function. If for some reason implementation details
need to change, it should be easy to do so by merely changing the
routines that perform the ADT operations. This change, in a perfect
world, would be completely transparent to the rest of the program.
There is no rule telling us which operations must be
supported for each ADT; this is a design decision. Error handling
and tie breaking (where appropriate) are also generally up to the
program designer. The three data structures that we will study in
this chapter are primary examples of ADTs. We will see how each
can be implemented in several ways, but if they are done correctly,
the programs that use them will not need to know which
implementation was used.
3.2 THE LIST ABSTRACT DATA TYPE:
We will deal with a general list of the form a
1
, a
2
, a
3
, . . . , a
n
.
We say that the size of this list is n. We will call the special list of
size 0 a null list.
For any list except the null list, we say that a
i+l
follows (or
succeeds) a
i
(i < n) and that a
i-1
precedes a
i
(i > 1). The first
element of the list is a
1
, and the last element is a
n
. We will not
define the predecessor of a
1
or the successor of a
n
. The position of
element a
i
in a list is i. Throughout this discussion, we will assume,
to simplify matters, that the elements in the list are integers, but in
general, arbitrarily complex elements are allowed.
Associated with these "definitions" is a set of operations that we
would like to perform on the list ADT. Some popular operations are
(a) print_list and make_null, which do the obvious things;
(b) find, which returns the position of the first occurrence of a key;
(c) insert and delete, which generally insert and delete some key
from some position in the list; and
(d) find_kth, which returns the element in some position (specified
as an argument).
If the list is 34, 12, 52, 16, 12, then find(52) might return 3;
insert(x,3) might make the list into 34, 12, 52, x, 16, 12 (if we insert